﻿#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<assert.h>
#include<ctype.h>
#include<errno.h>
#include<float.h>
#include<iso646.h>
#include<limits.h>
#include<locale.h>
#include<math.h>
#include<stdarg.h>
#include<stddef.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include<complex.h>
#include<stdbool.h>
#include<tgmath.h>
#include<signal.h>
#include<setjmp.h>
#include<inttypes.h>

//描述
//本道题要求你获得用户的输入，并输出对应的内容。
//例如输入的是
//Tom
//你应该输出：
//Hello World Tom!
//带换行，一个字符不能多，一个字符不能少。
//注意不要自作聪明地给出输入提示，OJ判题机只会把你的体贴当作对他智商的侮辱，
//给你个大大的X。简单获得用户输入即可。
//输入
//一个字符串，为用户的名字，例如
//Tom
//输出
//Hello World <用户输入的名字>!
//例如
//Hello World Tom!

//int main()
//{
//	char str[100] = { 0 };
//	scanf("%s", str);
//	printf("Hello World %s!", str);
//	return 0;
//}


//描述
//所有OJ的入门题，A + B。
//但本道题并不是普通的A + B，而是一道函数填空题，你会在答题区看到函数模板，
//你需要完成他，将参数a和b相加之后作为返回值返回。
//注意：你不需要（也不能）编写main函数的，否则会导致编译错误。
//计算输入的两个数值的和。
//输入
//函数的参数是两个用于相加的数字，例如：
//1 2
//输出
//两个数字的和，作为函数返回值返回。
//3
//int a_plus_b(int a, int b) {
//    return a+b;
//}

//描述
//已知华氏度和摄氏度的转换公式是：C = 5×(F−32) / 9，
//其中C为摄氏温度，F为华氏温度。
//请你编写一个摄氏度和华氏度的转换软件，用户输入华氏度之后，
//你输出摄氏度，精确到小数点后5位。
//输入
//一个浮点数，表示华氏度，例如：
//41
//输出
//对应的摄氏度，精确到小数点后5位，例如：
//5.00000

//int main() 
//{
//    double f;
//    scanf("%lf", &f);
//    printf("%.5f", 5 * (f - 32) / 9);
//    return 0;
//}

//描述
//输入3个整数，请你给出他们中最大的那个数字。
//输入
//3个整数，以空格隔开
//例如：
//10 20 56
//输出
//他们中最大的数字，带回车，例如
//56

//int compare(void* p1, void* p2)
//{
//	return (*(int*)p1 - *(int*)p2);
//}
//
//int main()
//{
//	int arr[3] = { 0 };
//	for (int i = 0; i < 3; i++)
//	{
//		scanf("%d",&arr[i]);
//	}
//	qsort(arr, 3, 4, compare);
//	printf("%d\n",arr[2]);
//	return 0;
//}


//三角形判断
//描述
//给定三个正整数，分别表示三条线段的长度，判断这三条线段能否构成一个三角形。
//输入
//输入共一行，包含三个正整数，分别表示三条线段的长度，数与数之间以一个空格分开。
//输出
//能构成三角形则输出true，否则输出false
//int main()
//{
//    int a, b, c;
//    scanf("%d%d%d", &a, &b, &c);//多次输入循环
//    {
//        if (a + b > c && b + c > a && a + c > b)
//        {
//            printf("true");
//        }
//        else
//        {
//            printf("false");
//        }
//    }
//    return 0;
//}

//描述
//有分段函数定义如下：
//当0≤x < 5时，y = −x + 2.5
//当5≤x < 10时，y = 2−1.5(x−3)(x + 3)
//当10≤x < 20时，y = x / 2−1.5
//请编写代码，根据输入的x给出对应的y的值。
//输入
//一个浮点数，表示x
//输出
//对应的y值，保留3位小数。
//如果x不在定义域内，输出n
//int main()
//{
//	double x;
//	scanf("%lf",&x);
//	double y;
//	if (x >= 0 && x < 5)
//	{
//		y = (-x) + 2.5;
//		printf("%.3lf", y);
//	}
//	else if (x >= 5 && x < 10)
//	{
//		y = 2 - (1.5 * (x - 3) * (x + 3));
//		printf("%.3lf", y);
//	}
//	else if (x >= 10 && x < 20)
//	{
//		y = (x / 2) - 1.5;
//		printf("%.3lf", y);
//	}
//	else
//	{
//		printf("n");
//	}
//	return 0;
//}


//描述
//如果一位同学只有一门课的成绩不及格，那么他还是可以挽救的，
//本道题要求你判断下某位学生是否还可以挽救。
//给出一名学生的语文、数学、英语成绩，
//判断他是否恰好有一门课不及格（成绩小于60分）。
//若该学生恰好有一门成绩不及格输出true，否则输出false。
//输入
//三门课的成绩，空格隔开
//输出
//如果可以挽救，输出true
//否则输出false
//int main()
//{
//	int a, b, c;
//	scanf("%d%d%d",&a,&b,&c);
//	if ((a < 60 && b >= 60 && c >= 60) || (b < 60 && a >= 60 && c >= 60) || (c < 60 && a >= 60 && b >= 60))
//	{
//		printf("true");
//	}
//	else
//	{
//		printf("false");
//	}
//	return 0;
//}

//描述
//跳格子是每个男孩子（误）都喜欢的游戏。
//我们按如下规则来进行跳格子，所有的格子共有7个格子，
//构成一个首尾相连的环，也即当你在第7号格子往前再走一步，就回到1号格子。
//给定一个步数，请你给出当停下来时，落在几号格子里，假设最初你停留在1号格子里。
//输入
//一个正整数，表示跳格子的步数。
//比如：
//1
//表示跳1步
//12
//表示跳12步
//输出
//输出结束时落在哪个格子里。
//例如：如果是1步，则落在2号格子里。
//如果是12步，走6步到达7号格子，下一步又到了1号格子，
//此时还差5步，所以最后落在6号格子里。
//注意步数可能会很多。
//int main()
//{
//	long long int a = 0;
//	scanf("%lld",&a);
//	printf("%d",(a+1)%7);//因为最初是在第一格，所以要记得加一，不难就相当于是从第0格开始的
//	return 0;
//}

//描述
//本道题要求你对小数进行向下取整，所谓向下取整就是得到比小数小的最大整数。
//例如1.2，比他小的最大整数是1。
//比如 - 3.2，比他小的最大整数是 - 4（这里要注意负数的大小比较）。
//输入
//一个浮点数，你可能需要以double来存放以保证精度
//输出
//比输入小的最大整数
//int main()
//{
//	double x;
//	scanf("%lf",&x);
//	if (x >= 0)
//	{
//		printf("%d", (int)x);
//	}
//	else//即x小于0的情况
//	{
//		if (((int)(x)-x) == 0)//当为负数整数的时候
//		{
//			printf("%.0lf",x);
//		}
//		else
//		{
//			printf("%d", (int)(x - 1));
//		}
//	}
//}

//描述
//用左，上，右，下四个数字可以定义一个矩形，
//矩形的左上角为（左，上），右下角为（右，下）
//比如：
//- 1 - 1 1 1
//定义了一个以(-1, -1)为左上角，和(1, 1)为右下角的矩形。
//注意计算机的坐标系里，一般以左边和上边为起点。
//而x, y两数字可以定义一个点。
//现在请你编写一个程序，判断某个点是否在某个矩形内部。
//输入
//第一行为描述矩形的四个数字，分别是左，上，右，下。
//第二行为两个数字，分别是x和y。
//所有数字都为整数。
//输出
//如果点在矩形内部，请输出true，否则输出false
//注意点如果在矩形的边线上，也算在矩形的内部。
//int main()
//{
//	int a, b, c, d;
//	int x, y;
//	scanf("%d%d%d%d",&a,&b,&c,&d);
//	scanf("%d%d",&x,&y);
//	if ((x >= a && x <= c) && (y >= b && y <= d))//shit，画图分析，去画出左上和右下，然后再看x和y应该在什么范围
//	{
//		printf("true");
//	}
//	else
//	{
//		printf("false");
//	}
//	return 0;
//}

//描述
//某国所得税的扣税方式是这样：1万元以上部分收税20% ；
//5000~10000元部分收税10 % ；1000 - 5000元部分收税5 % ；1000元以下部分免税。
//比如有人收入是15000。1万元以上部分是15000 - 10000 = 5000，
//这部分所得税为5000 * 20 %= 1000；
//5000~10000部分5000元，这部分所得税为5000 * 10 %= 500；
//1000~5000部分4000元，所得税4000 * 5 %= 200。
//全部所得税为：1000 + 500 + 200 = 1700。
//请编写一个程序，根据输入的收入，输出需要缴纳的所得税。结果保留2位小数。
//输入
//某人的月收入
//输出
//他应该缴纳的税款，保留两位小数
//int main()
//{
//	long int m = 0;
//	scanf("%ld",&m);
//	double f = 0;
//	if (m <= 1000)
//	{
//		printf("0.00");
//	}
//	else if (m > 1000)
//	{
//		if (m <= 5000)
//		{
//			printf("%.2lf",((m-1000)*0.05));
//		}
//		else if (m > 5000)
//		{
//			if (m >= 10000)
//			{
//				f = (m - 10000) * 0.2 + (5000) * 0.1 + (4000) * 0.05;
//				printf("%.2lf",f);
//			}
//			else//当钱少于10000但大于5000时
//			{
//				f = (m - 5000) * 0.1 + 4000 * 0.05;
//				printf("%.2lf", f);
//			}
//		}
//	}
//	return 0;
//}

//求平均数
//描述
//给定n个数字，请给出他们的平均值，保留两位小数
//输入
//第一行是数字n
//第二行开始的n行是具体的数字
//输出
//输出平均值，保留2位小数
//int main()
//{
//	int arr[10000] = { 0 };
//	int n = 0;
//	scanf("%d", &n);
//	for (int i = 0; i < n; i++)
//	{
//		scanf("%d",&arr[i]);
//	}
//	double sum = 0;//设置为浮点型，才能在下面的除运算中避免强制转换
//	for (int i = 0; i < n; i++)
//	{
//		sum += arr[i];
//	}
//	double ret = sum / n;
//	printf("%.2lf",ret);
//	return 0;
//}

//描述
//所谓调和级数，是n的倒数之和，即：
//f(n) = 1 / 1 + 1 / 2 + 1 / 3 + 1 / 4 + 1 / 5 + ....
//给定n，请求出当对应的调和级数的值
//输入
//只有一个数字n
//输出
//n项调和级数的值，保留两位小数。
//int main()
//{
//	int n = 0;
//	scanf("%d",&n);
//	double sum = 0;
//	for (int i = 1; i <= n; i++)
//	{
//		sum = sum + (1.0 / i);//依然要注意整型除整型会自动去尾
//	}
//	printf("%.2lf",sum);
//	return 0;
//}/

//描述
//还是调和级数，本道题要求你计算小于某个数f的最大调和级数的值。
//所谓调和级数，是倒数之和，即：
//f(n) = 1 / 1 + 1 / 2 + 1 / 3 + 1 / 4 + 1 / 5 + .... + 1 / n
//例如，当f = 2.0时，因为f(3) = 1 + 1 / 2 + 1 / 3 = 1.83333，
//f(4) = 2.08，因此结果应该为1.833333
//输入
//对应的数字f，注意f是浮点数。
//输出
//小于f的最大调和级数的值，保留6位小数。
//int main()
//{
//	double f = 0;
//	scanf("%lf",&f);
//	double sum = 0;
//	double gap = 0;
//	double min = 1;
//	double temp = 0;//要初始化
//	for (int i = 1; i <= 100000; i++)
//	{
//		sum = sum + (1.0 / i);//依然要注意整型除整型会自动去尾
//		gap = f - sum;
//		if (gap > 0)
//		{
//			if (gap < min)
//			{
//				min = gap;
//				temp = sum;
//			}
//		}
//		else//如果差距为负数了，那就直接终止循环
//		{
//			break;
//		}
//	}
//	printf("%.6lf",temp);
//	return 0;
//}

//描述
//李老师的课上学生总是两极分化非常严重，有些学生能考满分，有些学生能考0分。
//请你编写程序，帮助李老师计算最高分和最低分的差距。
//输入
//第一行是数字n，表示n个学生
//第二行是学生的成绩，以空格分隔，注意，分数有可能为负数，但分数只有整数。
//输出
//最高分和最低分的分差。
//int compare(void* p1, void* p2)
//{
//	return (*(int*)p1 - *(int*)p2);
//}
//
//int main()
//{
//	int arr[10000] = { 0 };
//	int n = 0;
//	scanf("%d",&n);
//	for (int i = 0; i < n; i++)
//	{
//		scanf("%d",&arr[i]);
//	}
//	qsort(arr, n, 4, compare);
//	printf("%d",arr[n-1]-arr[0]);
//	return 0;
//}

//每个人都要做斐波拉契数列
//描述
//斐波拉契数列是每个计算机学生都做过的题目，
//自然界中很多现象都跟斐波拉契数列有关，所谓斐波拉契数列是指如下序列：
//1 1 2 3 5 8 13 21 .....
//他的定义是，f(1) == f(2) == 1，f(n) = f(n - 1) + f(n - 2)
//请你给出斐波拉契数列的第n项。
//输入
//第一行是一个数字n，表示接下来会有几个数字。
//第二行是n个数字，以空格隔开。
//输出
//你需要输出所有所有数字对应的斐波拉契数列项的值，每个一行。

//long long int fun(int x)
//{
//	long long int a = 0;
//	long long int b = 1;
//	long long int c = 0;
//	if (x <= 2)
//	{
//		return 1;
//	}
//	else
//	{
//		for (int i = 2; i <= x; i++)
//		{
//			c = a + b;
//			a = b;
//			b = c;
//		}
//	}
//	return c;
//}
//
//int main()
//{
//	int n = 0;
//	scanf("%d",&n);
//	int arr[1000] = { 0 };
//	for (int i = 0; i < n; i++)
//	{
//		scanf("%d",&arr[i]);
//	}
//	for (int i = 0; i < n; i++)
//	{
//		printf("%lld\n", fun(arr[i]));
//	}
//	return 0;
//}

//描述
//顺通快递的收费标准如下：
//首重12元。
//超过1000克，每增加500克，快递费要增加5元，不足500也按500算。
//如果你选择航空快运，那么首重要增加5元，每增加500克的超重费增加1元。
//请你根据用户输入的重量，输出对应的快递费。
//输入
//一个数字和一个字符，数字表示快递的重量，以克为单位，
//只会是整数。字符如果为y，则表示准备使用航空速运，否则表示不准备使用。
//输出
//对应的快递费
//int main()
//{
//	long long m = 0;
//	scanf("%lld",&m);
//	int money = 12;
//	char ch = 0;
//	scanf(" %c",&ch);//因为我们按完数字之后，会按回车，那么字符就会把回车给吸收
//	if (ch != 'y')
//	{
//		if (m <= 1000)
//		{
//			printf("%d", money);
//		}
//		else//重量大于1000块的时候
//		{
//			while (m > 1000)
//			{
//				money = money + 5;
//				m = m - 500;//看大于1000有多少个500，m=1501的时候也能行
//			}
//			printf("%d",money);
//		}
//	}
//	else
//	{
//		money = money + 5;
//		if (m <= 1000)
//		{
//			printf("%d", money);
//		}
//		else//重量大于1000块的时候
//		{
//			while (m > 1000)
//			{
//				money = money + 6;
//				m = m - 500;//看大于1000有多少个500，m=1501的时候也能行
//			}
//			printf("%d", money);
//		}
//	}
//	return 0;
//}

//描述
//本道题画空心三角形，看下面的描述。
//注意，为避免歧义，需要你打印的空白部分已经用`.代替了，
//其他空白的区域不需要你打印空格。
//输入
//一个数字n
//输出
//一个边长为n的空心直角三角形
//int main() {
//    int n;
//    printf("请输入边长n: ");
//    scanf("%d", &n);
//
//    // 循环控制行数，从1到n
//    for (int i = 1; i <= n; i++) {
//        // 第一行、第二行和最后一行打印i个'*'
//        if (i == 1 || i == 2 || i == n) {
//            for (int j = 1; j <= i; j++) {
//                printf("*");
//            }
//        }
//        else {
//            // 中间行：第一个和最后一个位置打印'*'，其余打印'.'
//            printf("*");
//            for (int j = 2; j < i; j++) {
//                printf(".");
//            }
//            printf("*");
//        }
//        // 每行结束后换行
//        printf("\n");
//    }
//    return 0;
//}

//画棱形
//描述
//画对角线长度为n的棱形
//注意，为避免歧义，需要你打印的空白部分已经用`.代替了，
//其他空白的区域不需要你打印空格。
//输入
//数字n，n必为奇数
//输出
//对角线长度为n的棱形
//int main() {
//    int n;
//    scanf("%d", &n);
//    // 确保输入是奇数
//    if (n % 2 == 0) {
//        printf("请输入奇数！\n");
//        return 1;
//    }
//    int half = n / 2;
//    // 上半部分（包括中间行）
//    for (int i = 0; i <= half; i++) {
//        // 打印左边的点
//        for (int j = 0; j < half - i; j++) {
//            printf(".");
//        }
//        // 打印星号
//        for (int j = 0; j < 2 * i + 1; j++) {
//            printf("*");
//        }
//        printf("\n");
//    }
//    // 下半部分
//    for (int i = half - 1; i >= 0; i--) {
//        // 打印左边的点
//        for (int j = 0; j < half - i; j++) {
//            printf(".");
//        }
//        // 打印星号
//        for (int j = 0; j < 2 * i + 1; j++) {
//            printf("*");
//        }
//        printf("\n");
//    }
//    return 0;
//}

//画等腰三角形
//描述
//绘制一个底边长度为n的等腰三角形。
//注意，为避免歧义，需要你打印的空白部分已经用`.代替了，
//其他空白的区域不需要你打印空格。
//输入
//数字n，n一定为奇数
//输出
//底边长度为n的等腰三角形，实心。
//int main() {
//    int n;
//    // 输入底边长度n
//    scanf("%d", &n);
//    // 计算等腰三角形的层数，为(n + 1) / 2层
//    int layers = (n + 1) / 2;
//    for (int i = 0; i < layers; i++) {
//        // 打印每行前面的点，数量为(layers - 1 - i)个
//        for (int j = 0; j < layers - 1 - i; j++) {
//            printf(".");
//        }
//        // 打印每行的星号，数量为(2 * i + 1)个
//        for (int j = 0; j < 2 * i + 1; j++) {
//            printf("*");
//        }
//        // 每行结束后换行
//        printf("\n");
//    }
//    return 0;
//}

//描述
//本题要求你画底边长度为n的空心等腰三角形
//注意，为避免歧义，需要你打印的空白部分已经用`.代替了，
//其他空白的区域不需要你打印空格。
//输入
//底边边长n，n必为奇数。
//输出
//底边边长为n的等腰三角形
//int main() {
//    int n;
//    // 输入底边长度n
//    scanf("%d", &n);
//    // 计算等腰三角形的层数，为(n + 1) / 2层
//    int layers = (n + 1) / 2;
//    for (int i = 0; i < layers; i++) {
//        // 打印每行前面的点，数量为(layers - 1 - i)个
//        for (int j = 0; j < layers - 1 - i; j++) {
//            printf(".");
//        }
//        // 处理每行的星号和点（空心部分）
//        if (i == 0 || i == layers - 1) {
//            // 第一层和最后一层（底边）打印连续的星号
//            for (int j = 0; j < 2 * i + 1; j++) {
//                printf("*");
//            }
//        }
//        else {
//            // 中间层，首尾打印星号，中间打印点
//            printf("*");
//            for (int j = 0; j < 2 * i - 1; j++) {
//                printf(".");
//            }
//            printf("*");
//        }
//        // 每行结束后换行
//        printf("\n");
//    }
//    return 0;
//}

//描述
//你懂的，画对角线长度为n的空心棱形
//注意，为避免歧义，需要你打印的空白部分已经用`.代替了，
//其他空白的区域不需要你打印空格。
//输入
//数字n，n必为奇数
//输出
//对角线长度为n的空心棱形
//int main() {
//    int n;
//    scanf("%d", &n);
//    int mid = (n - 1) / 2;
//
//    for (int i = 0; i < n; i++) {
//        int d = abs(i - mid);
//        int start = d;
//        int end = n - 1 - d;
//
//        for (int j = 0; j < n; j++) {
//            if (j == start || j == end) {
//                putchar('*');
//            }
//            else {
//                putchar('.');
//            }
//        }
//        putchar('\n');
//    }
//
//    return 0;
//}

//求数字各位之和
//描述
//给定数字n，请你给出该数字各位数字之和
//输入
//单个数字n
//输出
//数字n的各位数字之和
//int main() {
//    int n;
//    // 输入数字 n
//    scanf("%d", &n);
//    int sum = 0;
//    // 当 n 不为 0 时，进行循环
//    while (n != 0) {
//        // 取 n 的个位数字并累加到 sum 中
//        sum += n % 10;
//        // 去掉 n 的个位数字
//        n /= 10;
//    }
//    // 输出各位数字之和
//    printf("%d\n", sum);
//    return 0;
//}

//描述
//请你把任意数制的数转换为对应的十进制数。
//例如：16进制的ABCDEF等于10进制的11259375。
//请注意是任意数制，并不仅限于10或者16或者8。
//输入
//一个数字和一个字符串
//数字表示数制的底，字符串为该数制下的数字，
//用大写的ABCDEF表示10~15的数，数制的底不会超过16。
//输出
//对应的十进制数字
// 字符转数值（处理0-9, A-F, a-f）
//int charToValue(char c) {
//    if (isdigit(c)) {
//        return c - '0';
//    }
//    else if (isupper(c)) {
//        return c - 'A' + 10;
//    }
//    else if (islower(c)) {
//        return c - 'a' + 10;
//    }
//    return -1; // 无效字符
//}
//
//int main() {
//    int base;
//    char str[1000] = { 0 };
//    scanf("%d", &base);
//    // 检查进制合法性
//    if (base < 2 || base > 36) {
//        printf("错误：进制必须在2-36之间\n");
//        return 1;
//    }
//    scanf("%s", str);
//    int len = strlen(str);
//    long long sum = 0; // 使用long long防止溢出
//    for (int i = 0; i < len; i++) {
//        int val = charToValue(str[i]);
//        // 检查字符是否符合当前进制
//        if (val == -1 || val >= base) {
//            printf("错误：输入的数不符合%d进制规则\n", base);
//            return 1;
//        }
//        // 按位计算十进制值
//        sum = sum * base + val;
//    }
//    printf("%lld", sum);
//    return 0;
//}

//描述
//3n + 1猜想又称角谷猜想，对于任意一个整数n，如果他是奇数，
//我们就令n = 3 * n + 1，
//如果是偶数，则令n = n / 2，重复这一过程，总会回到4、2、1这样的循环。
//请你用代码验证这一点。
//输入
//数字n
//输出
//将迭代的结果依次打印，一个数字一行。
//int main()
//{
//	long long int n = 0;
//	scanf("%lld",&n);
//	while (n != 1)
//	{
//		if (n % 2 == 0)
//		{
//			n = n / 2;
//		}
//		else
//		{
//			n = 3 * n + 1;
//		}
//		printf("%lld\n",n);
//	}
//	return 0;
//}

//求范围内的最大素数
//描述
//给定数字n（3 < n < 10 ^ 15），求n范围内最大的素数。
//所谓素数就是只能被自己和1整除的数。
//输入
//数字n（3 < n < 10 ^ 15）
//输出
//n范围内的最大素数。

//long long int fun(long long n)
//{
//	int flag = 1;
//	if (n <= 1) return 0;    // 1不是质数
//	if (n == 2) return 1;    // 2是质数
//	if (n % 2 == 0) return 0; // 偶数不是质数
//	for (long long int i = 3; i <= sqrt(n); i += 2)
//	{
//		if (n % i == 0)
//		{
//			flag = 0;
//		}
//	}
//	return flag;
//}
//
//int main()
//{
//	long long int n = 0;
//	scanf("%lld",&n);
//	long long int max = 0;
//	for (long long int i = n-1; i >= 2; i--)
//	{
//		if (fun(i))
//		{
//			max = i;
//			break;
//		}
//	}
//	printf("%lld",max);
//	return 0;
//}

//描述
//求两个整数n, m（3 < m, n < 10 ^ 15）的最大公约数。
//输入
//两个数字，m和n。
//输出
//这两个数字的最大公约数
//辗转相除法
//int main()
//{
//	long long m, n;
//	scanf("%lld%lld",&m,&n);
//	if (m > n)
//	{
//		while (m % n)
//		{
//			long long int c = n;
//			n = m % n;
//			m = c;
//		}
//		printf("%lld", n);
//	}
//	else
//	{
//		while (n % m)
//		{
//			long long int c = m;
//			m = n % m;
//			n = c;
//		}
//		printf("%lld",m);
//	}
//	return 0;
//}

//描述
//哥德巴赫猜想是计算机入门同学必做的一道题，他是这么说的：任意一个大于6的偶数，
//都可以表示为两个素数的和，例如：6 = 3 + 3，8 = 3 + 5，12 = 5 + 7等。
//请你编程来验证他。
//输入
//需要验证的偶数n(6 < n < 10 ^ 17)
//输出
//输出n = x + y，如果有多组结果，输出x和y相差最大的一组，且x < y。
//例如：20，可以表示成3 + 17，
//也可以表示称7 + 13，3和17的差比7和13大，因此你应该输出：20 = 3 + 17
//int fun(long long int n)
//{
//	if (n == 0)
//	{
//		return 0;
//	}
//	if (n == 1)
//	{
//		return 0;
//	}
//	if (n == 2)
//	{
//		return 1;
//	}
//	if (n % 2 == 0)//偶数除了2以外，全不是素数
//	{
//		return 0;
//	}
//	long long temp = sqrt(n);
//	for (long long int i = 3; i <= temp; i += 2)
//	{
//		if (n % i == 0)
//		{
//			return 0;
//		}
//	}
//	return 1;
//}
//
//int main()
//{
//	long long int n = 0;
//	scanf("%lld",&n);
//	long long int gap = 0;
//	long long int max = -1;
//	long long int x = 0;
//	long long int y = 0;
//	for (long long int i = 2; i <= n/2; i++)//遍历到n/2就行，因为我们后面是采取n-i的方式
//	{
//		if ((fun(i) && fun(n-i)) && (i <= (n-i)))//直接使用n-i进行判断，避免双重循环速度慢
//		{
//			gap = n - i - i;
//			if (gap > max)
//			{
//				max = gap;
//				x = i;
//				y = n-i;
//			}
//			break;
//			//由于我们从最小的质数i开始遍历，
//			//找到的第一对符合条件的(i, j)必然是差值最大的
//		    //（因为i越小，j = n - i越大，差值j - i越大）
//			//找到后立即break退出循环，无需继续检查后续数值
//		}
//	}
//	printf("%lld=%lld+%lld",n,x,y);
//	return 0;
//}

//描述
//所谓完数，是不包括自身的所有因子相加之后等于自身的数，例如：
//6的因子是1，2，3，而1 + 2 + 3 = 6，因此6是完数。
//请你打印出10000以内的所有完数，每个一行。
//输入
//无
//输出
//打印出10000以内的所有完数，一个一行。
//int fun(int n)
//{
//	//先求出n的所有因数
//	//同时进行相加
//	int sum = 0;
//	long long int temp = sqrt(n);
//	for (int i = 1; i <= temp; i++)//终止条件到sqrt(n)就行了，再大于就会和之前重复数字
//	{
//		if (n % i == 0)//能被整除
//		{
//			//此时就代表n/i以及i都是n的因数
//			//但是我们只加一个因数，要是把两个都加进去的，很明显会有问题
//			//比如1和6
// 
//			sum = sum + i;
// 
//			//同时我们为了避免重复相加，比如n==6
//			//那么i=1可以，i=2可以，又因为sqrt（6）==2
//			//那么我们就只能加1和2,3却不能加进去
//			//所以，我们还得通过判断将另一个因数即n/i加进去
//			//判断条件就是n/i！=i且不等于n，不难i为1的时候
//			//n/i可是为6，不等于1哦，但是6很明显不能加进去
// 
//			if (n / i != i && n / i != n)
//			{
//				sum = sum + n / i;
//			}
//		}
//	}
//	if (sum == n)
//	{
//		return 1;
//	}
//	else
//	{
//		return 0;
//	}
//}
//
//int main()
//{
//	for (int i = 1; i <= 10000; i++)
//	{
//		if (fun(i))
//		{
//			printf("%d\n", i);
//		}
//	}
//	return 0;
//}

//描述
//已知数字n是两个素数的乘积。请输出比较大的那个因数。
//输入
//数字n，n是两个素数的积。
//输出
//输出大的那个质因数。
//int fun(long long int n)
//{
//	if (n == 1 || n == 0)
//	{
//		return 0;
//	}
//	if (n == 2)
//	{
//		return 1;
//	}
//	if (n % 2 == 0)
//	{
//		return 0;
//	}
//	long long int temp = sqrt(n);
//	for (long long int i = 3; i <= temp; i += 2)
//	{
//		if (n % i == 0)
//		{
//			return 0;
//		}
//	}
//	return 1;
//}
//
//int main()
//{
//	long long int x = 0;
//	scanf("%lld", &x);
//	long long int temp = sqrt(x);
//	for (long long int i = 1; i <=temp ; i++)//和上一题一样，我们依旧要去寻找因数
//	{
//		if ((x % i == 0) && (fun(i) && fun(x / i)))//既能被整除，又都是素数
//		{
//			if (x / i > i)
//			{
//				printf("%lld",x/i);
//			}
//			else
//			{
//				printf("%lld",i);
//			}
//		}
//	}
//	return 0;
//}

//只要是求因数，就和sqrt脱不了关系，希望注意

//描述
//逆转输入的内容并输出。
//注意本道题不提供输入数字的个数，也就是你们熟悉的OJ题目可能是：
//10
//1 2 3 4 5 6 7 8 9 10
//先用第一个10给出后续输入的数字的个数，再给具体的数据。
//但有一类数据的输入是这样：
//1 2 3 4 5 6 7 8 9 10
//并不在一开始给你输入的数据量，直接给你一条，你要读完才知道有几个。
//这种情况下你需要通过通过stdin的EOF来判断输入是否结束。
//你需要将输入的数字逆向打印出来，以空格隔开
//输入
//一串数字，以空格分隔，数字的数目 < 10 ^ 6。
//输出
//输入的逆序，以空格分隔。
//int main()
//{
//	long long int n = 0;
//	long long int arr[10000] = { 0 };
//	int sign = 0;
//	while (scanf("%lld", &n)!=EOF)
//	{
//		arr[sign++] = n;
//	}
//	for (int i = sign - 1; i >= 0; i--)
//	{
//		printf("%lld ",arr[i]);
//	}
//	return 0;
//}

//描述
//给定一串数字（数目N <= 2 * 10 ^ 7），
//请你给出每个数字出现的次数。数字范围在1~1000以内。
//输入
//一串数字，例如：
//1 1 1 2 2 2 3 3 10
//输出
//你需要给出出现过的数字的出现次数，从小到大依次输出。
//每一行一个数字，上例中应该输出：
//1 3
//2 3
//3 2
//10 1

//双重循环
//int main()
//{
//	int n = 0;
//	int arr[10000000] = { 0 };
//	int sign = 0;
//	while (scanf("%d", &n) != EOF)
//	{
//		arr[sign++] = n;
//	}
//	int count = 0;//计数
//	for (int i = 0; i <= 1000; i++)
//	{
//		for (int j = 0; j < sign; j++)
//		{
//			if (arr[j] == i)
//			{
//				count++;
//			}
//		}
//		if (count != 0)
//		{
//			printf("%d %d\n", i, count);
//			count = 0;//将计数器重置为0，便于下次再计数
//		}
//	}
//	return 0;
//}

//采取计数数组
//nnd，真是个好办法
//妙啊
//int main()
//{
//	int arr[10000] = { 0 };
//	int n = 0;
//	while (scanf("%d", &n) != EOF)
//	{
//		arr[n]++;
//	}
//	for (int i = 0; i < 10000; i++)
//	{
//		if (arr[i] > 0)
//		{
//			printf("%d %d\n",i,arr[i]);
//		}
//	}
//	return 0;
//}

//描述
//输入一组数据，请你去掉其中多余的数字。输出时请按数字第一次出现的为止输出。
//输入
//一行数据。
//例如：
//1 3 2 1 3 1 2 3 4
//输出
//输出去重后的数字，每个数字只在第一次出现的位置输出，以上例而言，应该输出：
//1 3 2 4
//int main()
//{
//	int n = 0;
//	int arr[1000000] = { 0 };
//	int arr1[1000000] = { 0 };
//	int sign = 0;
//	while (scanf("%d", &n) != EOF)
//	{
//		arr[n]++;
//		arr1[sign++] = n;
//	}
//	for (int i = 0; i < sign; i++)
//	{
//		if (arr[arr1[i]] > 0)
//		{
//			printf("%d ",arr1[i]);
//			int temp = arr1[i];
//			//这里注意，如果我们不用临时变量去保存arr1[i]的话，
//			//那么经历了下面的删除之后，就会找不到这个值了
//			for (int j = 0; j < sign; j++)
//			{
//				if (arr1[j] == temp)
//				{
//					arr1[j] = -1;
//				}
//			}
//		}
//	}
//	return 0;
//}

//int main()
//{
//	int n = 0;
//	int sign = 0;
//	int arr[100000] = { 0 };
//	while (scanf("%d", &n)!=EOF)
//	{
//		arr[sign++] = n;
//	}
//	for (int i = 0; i < sign; i++)
//	{
//		int flag = 0;
//		for (int j = 0; j < i; j++)//不能等于i
//		{
//			if (arr[j] == arr[i])
//			{
//				flag = 1;
//				break;
//			}
//		}
//		if (flag != 1)//要注意是flag不等于1，即之前没有出现过类似的
//		{
//			printf("%d ",arr[i]);
//			//1 3 2 1 3 1 2 3 4
//		}
//	}
//	return 0;
//}

//描述
//矩阵相乘是线性代数（头开始疼了）的基础操作。
//请你编写一个用来计算矩阵相乘的程序：
//矩阵相乘的计算过程是这样的：
//一个m行n列的矩阵（a）和n行k列的矩阵（b）才可以相乘，
//结果得到一个m行k列的矩阵（c）。
//结果矩阵的第i行，第j列元素元素的值
//c(i, j) = a(i, 1) * b(1, j) + a(i, 2) * b(2, j) + ... + a(i, n) * a(n, j)
//以一个一个3行2列的矩阵
//a11 a12
//a21 a22
//a31 a32
//和2行4列的矩阵
//b11 b12 b13 b14
//b21 b22 b23 b24
//相乘为例。
//结果会得到一个3行4列的矩阵：
//a11 * b11 + a12 * b21  a11 * b12 + a12 * b22  a11 * b13 + a12 * b23  a11 * b14 + a12 * b24
//a21 * b11 + a22 * b21  a21 * b12 + a22 * b22  a21 * b13 + a22 * b23  a21 * b14 + a22 * b24
//a31 * b11 + a32 * b21  a31 * b12 + a32 * b22  a31 * b13 + a32 * b23  a31 * b14 + a32 * b24
//输入
//第一行输入m，n，k三个值，其中m，n，k都小于10
//接下来是第一个矩阵，有m行，n列。
//然后是第二个矩阵，有n行，k列。
//例如：
//3 2 4
//1 2
//2 1
//1 1
//1 2 3 1
//3 2 1 2
//第一行表示是一个3行2列的矩阵和一个2行4列的矩阵相乘
//接下来的3行是第一个矩阵。
//再下来的2行是第二个矩阵。
//输出
//计算的结果，以输入为例，应该得到一个3行4列的矩阵：
//7 6 5 5
//5 6 7 4
//4 4 4 3
//数字之间用空格隔开，注意每行的尾部有一个空格，不要吃掉他，
//用你最自然的输出方式输出。


//求N以内素数的数目
//描述
//是素数不是菽粟。
//给定数字N，请你给出N内素数的数目。2 < N <= 5 * 10 ^ 7。
//输入
//数字N
//输出
//小于N的素数的个数（不包括N）。
//注意1不是素数，2是素数。
//int fun(long long int n)
//{
//	if (n == 0 || n == 1)
//	{
//		return 0;
//	}
//	if (n == 2)
//	{
//		return 1;
//	}
//	if (n % 2 == 0)
//	{
//		return 0;
//	}
//	long long int SQRT = sqrt(n);
//	for (long long int i = 3; i <= SQRT; i += 2)
//	{
//		if (n % i == 0)
//		{
//			return 0;
//		}
//	}
//	return 1;
//}
//
//int main()
//{
//	long long int n = 0;
//	scanf("%lld",&n);
//	long long int count = 0;
//	if (2 <= n)
//	{
//		count++;
//	}
//	for (long long int i = 3; i < n; i += 2)//只考虑奇数
//		//那么就要注意的点了，因为我们是只考虑奇数，所以i也只能从奇数开始，不能从0或者偶数开始
//	{
//		if (fun(i))
//		{
//			count++;
//		}
//	}
//	printf("%lld",count);
//	return 0;
//}

// 埃氏筛法计算小于n的素数个数
//int countPrimes(long long int n) {
//    if (n <= 2) return 0;
//
//    // 创建素数标记数组，isPrime[i]为1表示i是素数
//    char* isPrime = (char*)malloc(n * sizeof(char));
//    if (isPrime == NULL) {
//        fprintf(stderr, "内存分配失败\n");
//        return -1;
//    }
//
//    // 初始化：默认所有数都是素数
//    for (long long int i = 2; i < n; i++) {
//        isPrime[i] = 1;
//    }
//
//    // 筛选过程
//    for (long long int i = 2; i * i < n; i++) {
//        if (isPrime[i]) {  // 如果i是素数，标记其倍数为非素数
//            for (long long int j = i * i; j < n; j += i) {
//                isPrime[j] = 0;
//            }
//        }
//    }
//
//    // 统计素数个数
//    long long int count = 0;
//    for (long long int i = 2; i < n; i++) {
//        if (isPrime[i]) {
//            count++;
//        }
//    }
//
//    free(isPrime);
//    return count;
//}
//
//int main() {
//    long long int n;
//    scanf("%lld", &n);
//    printf("%lld\n", countPrimes(n));
//    return 0;
//}

//描述
//本道题要求你移除单词的后缀，一共有3中后缀需要你去除：ly，er和ing。
//如果单词不包含这些后缀，原样输出即可。
//输入
//待处理的单词。单词的长度很短，都不超过20。
//输出
//处理之后的结果。
//int main()
//{
//	char str[1000] = { 0 };
//	scanf("%s",str);
//	int len = strlen(str);
//	if (str[len - 1] == 'y' && str[len - 2] == 'l')
//	{
//		for (int i = 0; i < len - 2; i++)
//		{
//			printf("%c",str[i]);
//		}
//	}
//	else if (str[len - 1] == 'r' && str[len - 2] == 'e')
//	{
//		for (int i = 0; i < len - 2; i++)
//		{
//			printf("%c", str[i]);
//		}
//	}
//	else if (str[len - 1] == 'g' && str[len - 2] == 'n' && str[len - 3] == 'i')
//	{
//		for (int i = 0; i < len - 3; i++)
//		{
//			printf("%c", str[i]);
//		}
//	}
//	else
//	{
//		printf("%s",str);
//	}
//	return 0;
//}

//描述
//我们经常在比赛中听到这样的话：去掉一（N）个最高分，去掉一（N）个最低分，
//最后得分是……
//这是为了尽量避免极端分数对总分的影响。
//举例来说，如果10名裁判打分依次是：
//1 2 3 4 5 6 7 8 9 10
//要求去掉2个最高分，2个最低分，那么最后的得分是：
//(3 + 4 + 5 + 6 + 7 + 8) / 6 = 5.5
//请你给出计算的程序。
//输入
//第一行是两个数字n m，分别表示有n个裁判，要求去掉m个最高分和m个最低分。
//其中10 < n <= 20000，2 < m <= 500
//接下来的一行是所有裁判的打分，分数不会超过100。
//输出
//输出选手的得分，保留两位小数。
//int compare(void* p1, void* p2)
//{
//	return *(int*)p1 - *(int*)p2;
//}
//
//int main()
//{
//	int n, m;
//	scanf("%d%d",&n,&m);
//	int arr[20001] = { 0 };
//	for (int i = 0; i < n; i++)
//	{
//		scanf("%d",&arr[i]);
//	}
//	qsort(arr, n, 4, compare);
//	double avg = 0;//记得用小数防止自动强制转换
//	long long int sum = 0;//记得用小数防止自动强制转换
//	for (int i = m ; i < n - m; i++)
//	{
//		sum += arr[i];
//	}
//	avg = (sum*1.0) / (n - 2 * m);
//	printf("%.2lf",avg);
//	return 0;
//}

//描述
//计算排列函数p(n, m)的值。排列函数如何计算请自行处理。
//输入
//函数参数，n是底，m是排列元素的数目。
//例如p(3, 2)表示在3个元素中选择2个元素进行排列，可形成的排列的数目。
//输出
//输出排列的数目。
//上例中，应该输出6。
//long long p(long long n, long long m) {
//    if (m < 0 || m > n) {
//        return 0;  // m为负或m>n时，排列数为0
//    }
//    if (m == 0) {
//        return 1;  // 0个元素的排列数为1
//    }
//    long long int ret = 1;
//    for (long long int i = 0; i < m; i++)
//    {
//        //P(n, m) = n×(n - 1)×...×(n - m + 1)
//        ret *= (n - i);
//    }
//    return ret;
//}
//
//int main()
//{
//    printf("%lld",p(3,2));
//    return 0;
//}

//描述
//本道题计算组合数c(n, m)。
//输入
//参数n和m分别为元素总数和待选元素的数目。
//比如c(3, 2)表示从3个元素里选两个元素的组合的数目。
//输出
//返回结果。上例中，应该返回3。
//long long c(long long n, long long m) 
//{
//    //C(n, m) = [n ×(n - 1) ×(n - 2) × … ×(n - m + 1)] / [m ×(m - 1) × … × 1]
//    long long int sum = 1;
//    for (int i = 0; i < m; i++)
//    {
//        sum *= (n - i);
//    }
//    long long int sum1 = 1;
//    for (int i = m; i >= 1; i--)
//    {
//        sum1 *= i;
//    }
//    long long int ret = sum / sum1;
//    return ret;
//}

//int main()
//{
//    printf("%lld",c(3,2));
//    return 0;
//}

//描述
//例如：12345678，应该返回87654321， - 123456789，应该返回 - 987654321。
//输入
//不解释，数字的绝对值不大于10 ^ 10
//输出
//不解释
//int reverse_number(int n) {
//    char arr[1000] = { 0 };
//    sprintf(arr, "%d", n);
//    char arr1[1000] = { 0 };
//    int sign = 0;
//    for (int i = strlen(arr) - 1; i >= 0; i--)
//    {
//        arr1[sign++] = arr[i];
//    }
//    int ret = atoi(arr1);
//    if (n < 0)//如果是负数，就给它乘个负一转换为负数
//    {
//        ret = -1 * ret;
//    }
//    return ret;
//}

//int main()
//{
//    int n = 0;
//    scanf("%d",&n);
//    printf("%d", reverse_number(n));
//    return 0;
//}

//描述
//本道题请你用函数来解决哥德巴赫猜想，本道题有两个函数要求你编写：
//bool is_primer(long long n); // C++版本
//int is_primer(long long n);  // C语言版本
//和long long min_prime_of_goldbach(long long n);
//is_primer函数判断某个数字是不是素数，min_prime_of_goldbach输出符合哥德巴赫猜想的素数对里，
//最小的那个数字。
//注意，本道题有两个函数的本意，就是让你在一个函数里使用另一个函数，
//完成之后，再对照一下不使用函数的写法，思考下，这两种写法有什么区别，
//哪种更好？
//输入
//两个函数的入参都非常清楚，不解释。
//输出
//如果入参不是素数，is_prime返回false或者0，分别对应C++和C版本，否则返回true或者1。
//min_prime_of_goldbach返回符合要求的素数组合中最小的那个素数。
//比如20，既可以是3 + 17，也可以是7 + 13，此时你应该返回3。
//int is_prime(long long int n)
//{
//	if (n == 0 || n == 1)
//	{
//		return 0;
//	}
//	if (n == 2)
//	{
//		return 1;
//	}
//	if (n % 2 == 0)
//	{
//		return 0;
//	}
//	long long int SQRT = sqrt(n);
//	for (long long int i = 3; i <= SQRT; i += 2)
//	{
//		if (n % i == 0)
//		{
//			return 0;
//		}
//	}
//	return 1;
//}
//
//long long min_prime_of_goldbach(long long n) {
//	long long int gap = 0;
//	long long int max = -1;
//	long long int x = 0;
//	long long int y = 0;
//	for (long long int i = 2; i <= n/2; i++)//遍历到n/2就行，因为我们后面是采取n-i的方式
//	{
//		if ((is_prime(i) && is_prime(n-i)) && (i <= (n-i)))//直接使用n-i进行判断，避免双重循环速度慢
//		{
//			gap = n - i - i;
//			if (gap > max)
//			{
//				max = gap;
//				x = i;
//				y = n-i;
//			}
//			break;
//			//由于我们从最小的质数i开始遍历，
//			//找到的第一对符合条件的(i, j)必然是差值最大的
//		    //（因为i越小，j = n - i越大，差值j - i越大）
//			//找到后立即break退出循环，无需继续检查后续数值
//		}
//	}
//	return x;
//}

//int main()
//{
//	printf("%d", min_prime_of_goldbach(20));
//	return 0;
//}

//描述
//给定一串字符串，请输出非数字字符的数目。
//注意字符串中可能包含空格等非字母字符。
//输入
//一行字符串，长度 < 100。
//输出
//字符串中非数字字符的数目。
//int main()
//{
//	char str[100] = { 0 };
//	fgets(str,100,stdin);//使用fgets函数去避免字符串中有空格，scanf遇到就不吸收了
//	//fgets 会将输入的换行符 \n 存入 str
// int count = 0;
//	for (int i = 0; i < strlen(str)-1; i++)//因为数组最后有个换行符，所以会把这个给算上
//		//就是在str[strlen(str)-1]上，所以我们要把它忽略
//	{
//		if (!isdigit(str[i]))
//		{
//			//要注意数字存进字符数组中，也就变成了字符1 2 3等等，而不是普通的数字
//			count++;
//		}
//	}
//	printf("%d",count);
//	return 0;
//}

//描述
//我们知道DNA由两条互补的碱基链以双螺旋的方式结合而成。
//而构成DNA的碱基共有4种：A，G，T和C。
//其中A和T配对，G和C配对。
//本道题要求你根据其中一条链，给出整条DNA链的形式。
//输入
//一行字符串，只包含，AGTC这四个字符，例如：
//ATATGGATGGTGTTTGGCTCTG
//字符串的长度不大于5000。
//输出
//你要给出整条DNA的形式，第一行是输入链，第二行是表示连接的 | 字符。
//第三行是另一条基因链，如上例，应该输出：
//ATATGGATGGTGTTTGGCTCTG
//||||||||||||||||||||||
//TATACCTACCACAAACCGAGAC
//int main()
//{
//	char str[1000] = { 0 };
//	fgets(str, 1000, stdin);
//	printf("%s", str);
//	int count = strlen(str);
//	for (int i = 0; i < count-1; i++)
//	{
//		printf("|");
//	}
//	printf("\n");
//	char str1[1000] = { 0 };
//	int sign = 0;
//	for (int i = 0; i < count; i++)
//	{
//		if (str[i] == 'A')
//		{
//			str1[sign++] = 'T';
//		}
//		else if(str[i]=='T')
//		{
//			str1[sign++] = 'A';
//		}
//		else if (str[i] == 'G')
//		{
//			str1[sign++] = 'C';
//		}
//		else if (str[i] == 'C')
//		{
//			str1[sign++] = 'G';
//		}
//	}
//	printf("%s",str1);
//	return 0;
//}

//描述
//小明很不注意英语拼写，经常把大小写随便写，比如他这样写：
//hEllo
//HOW are You!
//等等，李老师快给他气死了，请你编写一个程序来帮他纠正拼写。
//纠正拼写的要求如下：
//任意一行字符，如果首字母是26个英语字符，那么他应该大写。
//行中的任何一个英语字符都应该小写。
//除此之外的所有字符都应该原样保留。
//因此：hEllo要转为Hello，HOW are You!要转为How are you!。
//2 - PENICILLIN应该转为2 - penicillin等等。
//输入
//第一行是数字n，表示要处理的行数，n不大于5000。
//接下来的n行为要你处理的字符串，注意可能包含空格。
//例如：
//3
//hEllo
//HOW are You
//Fine Thank you AND YOU ?
//第一行表示要你处理的数据有3行，接下来的3行是要你处理的数据。
//每行字符串的长度不超过50。
//输出
//输出纠正后的结果，一行行输出，例如上面的例子，应该输出：
//Hello
//How are you
//Fine thank you and you ?
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);//这个按的回车，可能会被后面给吸收了
//	getchar();//把上面按的回车给吸收了
//	char str[n][50];//创建二维数组
//	for (int i = 0; i < n; i++)
//	{
//		//对二维数组的每一行进行存储
//		fgets(str[i], 50, stdin);//要记得数组是从0开始存储的
//	}
//	for (int i = 0; i < n; i++)
//	{
//		if (islower(str[i][0]))//每一行的第一个字符
//		{
//			str[i][0] -= 32;//将小写字母转换为大写字母
//		}
//		for (int j = 1; j < 50; j++)
//		{
//			if (isupper(str[i][j]))//如果是大写字母
//			{
//				str[i][j] += 32;//将大写字母转换为小写字母
//			}
//		}
//	}
//	//将每行字符数组打印出来
//	for (int i = 0; i < n; i++)
//	{
//		//不要逐个打印出来，因为有可能打印出乱码或者其他没用的东西
//		printf("%s",str[i]);
//	}
//	return 0;
//}

//描述
//所谓回文串，就是对称的字符串，从头读到尾和从尾读到头，他们的结果是一样的。
//例如：
//abcdedcba
//就是回文
//而：
//abcdedcbb
//就不是。
//给定一个字符串，请你判断他是不是回文串。
//输入
//一行字符串，就是要你判断的字符串。字符串长度不超过100。
//输出
//如果是，则输出yes，否则输出no。
//int main()
//{
//	char str[100] = { 0 };
//	scanf("%s",str);
//	int sign = 0;
//	char reversestr[100] = { 0 };
//	int count = strlen(str);
//	for (int i = count-1; i >= 0; i--)
//	{
//		reversestr[sign++] = str[i];
//	}
//	int flag = 1;//判断标志
//	//abcdedcbb
//	for (int i = 0; i < sign; i++)
//	{
//		if (reversestr[i] != str[i])
//		{
//			flag = 0;
//			break;//直接终止循环，避免效率低下
//		}
//	}
//	if (flag == 0)
//	{
//		printf("no");
//	}
//	else
//	{
//		printf("yes");
//	}
//	return 0;
//}

//描述
//涂鸭梨学姐想知道班上谁是处女座男孩纸，
//已知处女座的日期为：8月23日 - 9月22日。
//要求，输入学生的性别和出生年月信息，输出该生是否处女座男孩。
//输入
//输入为一行，包括sex和birthday两个字段，空格间隔。
//其中sex取值为M（男）或F（女），birthday为8位出生年月信息，
//例如19980902（年月不足两位用前导0补齐）。
//输出
//如果是输出YES，否则输出NO。
//int main()
//{
//	char sex = 0;
//	scanf("%c",&sex);
//	getchar();
//	int b = 0;
//	scanf("%d",&b);
//	char str[100] = { 0 };
//	sprintf(str, "%d", b);
//	//1 9 9 8 0 9 0 2
//    //0 1 2 3 4 5 6 7
//	int month = str[5] - '0';
//	int day = ((str[6] - '0') * 10) + (str[7] - '0');
//	if (month >= 8 && month < 9 && day >= 23 && day <= 31)//8月份
//	{
//		if (sex == 'M')
//		{
//			printf("YES");
//		}
//		else
//		{
//			printf("NO");
//		}
//	}
//	else if (month > 8 && month <= 9 && day <= 22 && day >= 1)//9月份
//	{
//		if (sex == 'M')
//		{
//			printf("YES");
//		}
//		else
//		{
//			printf("NO");
//		}
//	}
//	else
//	{
//		printf("NO");
//	}
//	return 0;
//}

//描述
//天猫双11商品跨店每满200减30元，如满200 - 30，满400 - 60，
//以此类推，88VIP再95折，晓璐喜欢买买买，但她最讨厌做计算题，
//请你帮晓璐算一下她最终要支付多少钱。
//输入
//输入两个整型数字，以空格间隔。
//第一个数字是商品的价格，整型。(1 ≤ 商品价格 ≤ 1000)。
//第二个数字判断是否是88VIP，是88VIP值为1，不是88VIP值为0。
//输出
//输出一个实数。
//晓璐需要支付的钱，保留两位小数。
//提示
//如果不是88VIP，每满200减30元，590元满2个200可以减60，
//590 - 60 = 530。
//如果是88VIP，每满200减30元，590元满2个200可以减60，
//590 - 60 = 530，530 * 0.95 = 503.50。
//int main()
//{
//	int price = 0;
//	int vip = 0;
//	scanf("%d%d", &price, &vip);
//	if (vip == 1)//是vip
//	{
//		int n = price / 200;//590/200==2
//		while (n)
//		{
//			price -= 30;
//			n--;
//		}
//		printf("%.2f", price * 0.95);//整型*小数就变成了浮点型
//	}
//	else//不是vip
//	{
//		int n = price / 200;//590/200==2
//		while (n)
//		{
//			price -= 30;
//			n--;
//		}
//		printf("%.2lf",(double)price);//将整型price强制转换为double
//	}
//	return 0;
//}

//描述
//涂鸭梨学姐毕业后改行成了考古学家。
//这天，她从5000年前的古墓中挖出了一片甲骨，上刻着一串火星文字，
//其中包含现代英文字母和其他文字。
//假如认定连续存在的一串英文字母为一个单词，
//现在涂鸭梨学姐想统计一下该甲骨上的一串火星文字中存在多少个英文单词，
//请编写程序帮涂鸭梨学姐解决这一问题。
//输入
//输入1行，包含英文字母和其他字符(不超过80字符)，表示甲骨上的火星文。
//输出
//输出1个数字，表示所输入字符串中所含英文单词的个数。
//int main()
//{
//	char str[100] = { 0 };
//	fgets(str, 100, stdin);//因为有可能会有空格输入，那么此时就不能用scanf函数喽
//	int count = 0;//计数有几个英文单词
//	int len = strlen(str) - 1;//要记得减一，因为fgets函数会把换行给干进去，影响计数
//	for (int i = 0; i < len-1; i++)//因为下面有i+1，所以要len-1防止越界
//	{
//		//判断是不是英语单词的核心就是
//		//看是不是有连续两个字母或多个
//		//是的话，就代表是英文单词
//		if (isalpha(str[i]))//是英文字母的话
//		{
//			if (!isalpha(str[i + 1]))//如果一个英文字母之后不是因为字母的话
//				//就代表这不是一个英文单词
//			{
//				continue;
//			}
//			else
//			{
//				while (isalpha(str[i]))
//				{
//					i++;//让i直接干到不是英文字母的位置
//				}
//				count++;//计数加一
//			}
//		}
//		//让for循环从非英文字符开始循环
//		//接着就是重复上面的操作
//		//我们已经在上面的i++直接改变i了，所以我们在这里不用再改变i
//	}
//	printf("%d",count);
//	return 0;
//}

//描述
//涂鸭梨学姐梦想加入女篮，该死的队长给她一个任务，
//要她分析球队篮球运动特征数据，以便决定是否接收。
//已知：校队所用篮球每次从 h（米）高度自由落下，
//触地后会反弹到原高度的一半，再落下，会再反弹，……，
//如此反复。请编写程序，帮涂鸭梨学姐求出篮球在第 n 次落地时，
//球在空中一共经过多少距离？第 n 次反弹的高度是多少？(输出保留2位小数)
//输入
//输入1行，包含1个实数和1个整数，表示篮球初始时所处高度h和反弹的次数n。
//输出
//输出2个数，第1个数表示第n次着地时，球在空中经过的路程(长度)；
//第2个表示第 n 次反弹的高度，两数间以空格分隔。
//int main()
//{
//	double h;
//	int n;
//	scanf("%lf%d",&h,&n);
//	double sum = 0;//记录球在空中经过的路程(长度)
//	//这个也得算上落地后上升所运动的距离
//	double nh = 0;///记录第 n 次反弹的高度
//	while (n)
//	{
//		sum += h;//先加上最开始的高度
//		h = h / 2;//接着就得除2
//		n--;//次数减少一次
//		//但是我们要知道，当n==0的时候，是不用再算上上升的了
//		//但是由于我们还处于循环，所以就会加上
//		//那么这个时候我们就得借助循环了
//		if (n != 0)
//		{
//			sum += h;//因为要算上再上升的高度
//		}
//	}
//	printf("%.2lf %.2lf",sum,h);
//	return 0;
//}

//描述
//涂鸭梨学姐今天教小朋友学英文，今天这堂课是学习英语姓名简写。
//英语姓名的一般结构为：教名.自取名.姓。如 William.Jefferson.Clinton，
//学姐决定将英语姓名简写成教名.自取名，如William.Jefferson。
//请帮涂鸭梨学姐完成英语姓名简写。
//输入
//输入一个长度为M（ 5 < M < 40 ）的英语姓名，英文姓名中只有字母和.，
//格式为教名.自取名.姓，中间以.间隔。
//输出
//输出英语姓名简写。
//int main()
//{
//	char str[50] = { 0 };
//	fgets(str, 50, stdin);
//	//思路是找到第二个.
//	//然后记录这个点的位置
//	//再将字符数组从开始到这个点之前一个位置都给表达出来
//	int flag = 0;//记录下标
//	int count = 0;//记录出现了几次.
//	for (int i = 0; i < strlen(str) - 1; i++)
//	{
//		if (str[i] == '.')
//		{
//			count++;
//		}
//		if (count == 2)
//		{
//			flag = i;//记录坐标
//			break;//一旦出现点的次数达到2，就可以直接终止循环
//		}
//	}
//	for (int i = 0; i < flag; i++)
//	{
//		printf("%c",str[i]);
//	}
//	return 0;
//}

//描述
//涂鸭梨学姐毕设选题是开发游戏《鸭梨大冒险》。
//已知游戏副本中邪恶BOSS的地图坐标为（X, Y）。
//主角鸭梨使用装甲车发射出N枚炮弹，分别落在N个坐标上，
//每个炮弹能够攻击其半径R范围内的圆形区域（包括边界R），
//攻击力为A（使得被攻击到的敌人血值少A）。
//已知BOSS初始血值是100，发动这波炮弹攻击后，
//BOSS还剩多少血（当敌人被干掉时，血值变为0）？
//输入
//第一行输入两个实数（X, Y），空格间隔，表示BOSS地图坐标
//第二行输入两个整数R和A，分别表示炮弹攻击半径和攻击力
//第三行输入一个整数N，表示炮弹个数
//接下来是N行，每行两个实数(x, y)，空格间隔，表示炮弹攻击的坐标
//输出
//输出为一个整数，表示BOSS剩余血值

//struct zuo
//{
//	double x;
//	double y;
//};
//
//int main()
//{
//	double X, Y;
//	scanf("%lf%lf",&X,&Y);
//	int r, a;
//	scanf("%d%d",&r,&a);
//	int n;
//	scanf("%d",&n);
//	struct zuo arr[100];//结构体数组用于存储坐标
//	for (int i = 0; i < n; i++)
//	{
//		scanf("%lf%lf",&(arr[i].x),&(arr[i].y));
//	}
//	int init = 100;
//	for (int i = 0; i < n; i++)
//	{
//		//计算点到圆心的 欧几里得距离：
//		//距离公式为 dist = √[(X - x0)² + (Y - y0)²]。
//		//碰撞条件：
//		//若 dist ≤ r，则点在圆内（发生碰撞）；反之则无碰撞。
//		double dx = X - arr[i].x;
//		double dy = Y - arr[i].y;
//		double dist_sq = dx * dx + dy * dy;
//		if (dist_sq <= r * r)
//		{
//			init -= a;
//			if (init <= 0)  // 修正：防止血量变成负数
//			{
//				init = 0;
//				break;
//			}
//		}
//	}
//	printf("%d",init);
//	return 0;
//}

//描述
//涂鸭梨学姐通过了最后两门考试，现到医院药房做药品管理工作，
//其中，病人取药的管理是一项重要的任务，人工管理起来太麻烦了，
//涂鸭梨学姐想利用专业技术优势，使用计算机来帮助管理。
//假设对于任意一种药品，每天开始工作时的库存总量已知，
//并且一天之内不会通过进货的方式增加。
//每天会有很多病人前来取药，每个病人希望取走不同数量的药品。
//如果病人需要的数量超过了当时的库存量，药房会拒绝该病人的请求。
//涂鸭梨学姐希望知道每天会有多少病人没有取上药。
//输入
//共 3行。
//第一行是每天开始时的药品总量 m(1 ≤ m ≤ 1000)；
//第二行是这一天取药的人数 n(0 < n ≤ 100)；
//第三行共有 n个正整数，分别记录了每个病人希望取走的药品数量
//（按照时间先后的顺序，不超过 1000），两数之间以空格分隔。
//输出
//输出一个整数，表示这一天没有取上药品的人数。
//int main()
//{
//	int m = 0;
//	int n = 0;
//	int arr[200] = { 0 };
//	scanf("%d%d",&m,&n);
//	for (int i = 0; i < n; i++)
//	{
//		scanf("%d", &arr[i]);
//	}
//	int count = 0;//记录有多少个人取走了药品
//	for (int i = 0; i < n; i++)
//	{
//		if (m >= arr[i])
//		{
//			m -= arr[i];
//			count++;
//		}
//		else//代表当前库存无法支撑某一个人的购买量
//		{
//			//虽然剩余库存无法满足这个一个人
//			//但是可能满足下面的人，我们依旧要进行判断
//			continue;
//		}
//	}
//	int ret = n - count;
//	printf("%d",ret);
//	return 0;
//}

//描述
//已知鼓浪屿门票原价80元，但作如下规定：6岁（包含）以下孩童免票游玩，
//7岁到18岁（包含）成年人票价打八折，50岁（包括）以上年龄段票价打六折，
//其它年龄段按原价支付。一个旅游团有N人，并且知道每个人的年龄，
//请问该团一共需要支付多少钱？
//输入
//第一行输入一个正整数N （1 < N <= 10000），表示旅游团总人数
//第二行输入N个正整数，表示N个人的年龄，空格隔开
//输出
//输出一个整数M，表示需要的总票价
//int main()
//{
//	int n = 0;
//	scanf("%d",&n);
//	long long int m = 0;
//	int arr[100001] = { 0 };
//	for (int i = 0; i < n; i++)
//	{
//		scanf("%d",&arr[i]);
//	}
//	for (int i = 0; i < n; i++)
//	{
//		if (arr[i] <= 6)
//		{
//			m += 0;
//		}
//		else if (arr[i] >= 7 && arr[i] <= 18)
//		{
//			m += 80 * 0.8;
//		}
//		else if (arr[i] >= 50)
//		{
//			m += 80 *0.6;
//		}
//		else
//		{
//			m += 80;
//		}
//	}
//	printf("%lld",m);
//	return 0;
//}

//描述
//出租车的计价标准为：起步价10元，超出3公里的部分每公里3元。
//你要搭乘出租车X公里，请问需要支付多少钱？
//输入
//输入一行一个整型数字，表示X。（1 <= X <= 100）
//输出
//输出一行一个整数表示需要支付多少钱。
//int main()
//{
//	int init = 10;
//	int x = 0;
//	scanf("%d",&x);
//	if (x > 3)
//	{
//		while (x > 3)
//		{
//			init += 3;
//			x--;
//		}
//		printf("%d", init);
//	}
//	else
//	{
//		printf("%d",init);
//	}
//	return 0;
//}

//描述
//一口井N米深，井底有一只蜗牛，蜗牛第一天白天能爬X米，
//每天晚上掉下2米（最多掉到井底），
//第一天之后每天白天能向上爬的距离只有前一天的95% 。
//请你计算蜗牛能否爬到井口，如果能，输出蜗牛在第几天爬到井口。
//输入
//输入数据包含两个实数N和X，N(0 < N <= 10000)代表井深，
//X(0 < X <= 10000)代表第一天白天蜗牛能爬多高。
//输出
//如果蜗牛能爬出井口输出爬出的天数，如果不能爬出井口输出 - 1.
int main()
{
	double n = 0;
	scanf("%lf",&n);
	double x = 0;
	scanf("%lf",&x);
	int day = 0;//如果蜗牛能爬出井口输出爬出的天数
	//当向上爬的距离小于夜晚掉下去的高度了，自然也就爬不出去了
	double gap = 0;//蜗牛和井口的距离
	int flag = 0;//判断标志
	while (x >= 2)
	{
		if (day == 0)
		{
			gap = n - x;//第一天要单独讨论
		}
		else
		{
			gap = n - ((n - gap) + x);
		}
		x *= 0.95;
		//就这么循环下去，直到gap==0或者向上爬的距离小于夜晚掉下去的高度
		day++;//天数加加
		if (gap <= 0)//有可能直接爬过头了
		{
			flag = 1;
			break;
		}
		gap += 2;//夜晚掉下2米,因为是夜晚，所以应该放在最后，不难在上面
		//的话，还在白天就掉下去了2米，这还玩个哈机密
	}
	if (flag == 0)
	{
		printf("-1");
	}
	else
	{
		printf("%d",day);
	}
	return 0;
}

//#include <stdio.h>
//
//int main()
//{
//    double well_depth = 0;  // 井深
//    scanf("%lf", &well_depth);
//
//    double climb = 0;       // 当天能爬的距离
//    scanf("%lf", &climb);
//
//    int day = 0;
//    double current_position = 0;  // 当前位置，从井底0开始
//    int flag = 0;
//
//    while (climb > 2)  // 当爬的距离小于等于下滑距离时，无法爬出
//    {
//        day++;  // 新的一天开始
//
//        // 白天：向上爬
//        current_position += climb;
//
//        // 检查是否爬出井口
//        if (current_position >= well_depth)
//        {
//            flag = 1;
//            break;
//        }
//
//        // 晚上：下滑2米
//        current_position -= 2;
//
//        // 爬行动态衰减
//        climb *= 0.95;
//    }
//
//    // 最后再检查一次，有可能最后一天的爬行动态刚好能爬出
//    if (!flag && climb >= 2)
//    {
//        day++;
//        current_position += climb;
//        if (current_position >= well_depth)
//        {
//            flag = 1;
//        }
//    }
//
//    if (flag)
//    {
//        printf("%d", day);
//    }
//    else
//    {
//        printf("-1");
//    }
//
//    return 0;
//}































































































